from collections import deque

from tree.TreeNode import TreeNode


class Tree:
    def __init__(self, root: TreeNode, number):
        self.number = number
        self.root = root
        self.nodes = []
        self.nodes.append(root)

    def add_node(self, node):
        self.nodes.append(node)

    def DFS(self):
        stack = deque()
        stack.appendleft(self.root)
        while len(stack) != 0:
            node = stack.popleft()

            if node.left.is_empty() and node.right.is_full(self.number) and not node.is_searched:
                return node

            for child in node.children:
                stack.appendleft(child)

        return None

    def trace(self, node: TreeNode):
        if node is None:
            print("no solution")
            return None

        node.is_searched = True
        path = deque()
        path.append(node)
        cur = node

        while cur.parent is not None:
            cur = cur.parent
            path.append(cur)

        path.reverse()
        return path
